#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
/*
 * 题目：输入一个非负数n，
 * 请计算0到n之间每个数字的二进制形式中1的个数，
 * 并输出一个数组。
 *
 * 例如，输入的n为4，由于0、1、2、3、4的二进制形式中1的个数分别为0、1、1、2、1，
 * 因此输出数组[0，1，1，2，1]。
 */

/*
 * solution 1    每次去掉一个1
 * 从前往后，不利用已经计算出来的结果
 *
 */
void countBits01(int num)
{
    vector<int> ans;
     for (unsigned int i = 0; i <= num; ++i)
     {
         int j = i;
         int cnt = 0;       // "1"的个数
         while (j != 0)
         {
             cnt++;         // 每次减少"1", 从头计算
            /*
             * j 中的的"1"比 j&(j-1)中的"1"多一个
             *
             */

             j = j & (j - 1);
         }
         ans.push_back(cnt);
     }

}

/*
 *     solution 2    每次去掉一个1
 *     从前往后，利用之前计算出来的结果
 *
 */
void countBits02(int num)
{
    /*
     *
     * i&（i-1）”将i的二进制形式中最右边的1变成0，
     * 也就是说，整数i的二进制形式中1的个数比“i&（i-1）”的二进制形式中1的个数多1。
     *
     * 很神奇, 这里的规律
     */
    vector<int> ans;
    ans.push_back(0);
     for (int i = 1; i <= num; ++i)
     {
         int pos = i & (i - 1);
         ans.push_back(ans[pos] + 1);
     }

}
/*
 * solution 3    每次去掉一个
 * 从前往后，利用之前计算出来的结果
 */
void countBits03(int num)
{
    vector<int> ans;
    ans.push_back(0);
    for (int i = 1; i <= num; ++i)
    {
        i % 2 ? ans.push_back(ans[i << 1] + 1) : ans.push_back(ans[i << 1]);
    }
    
    for (auto it = ans.begin(); it != ans.end(); ++it)
    {
        cout << *it << endl;
    }
}

int main()
{
    countBits01(4);
    return 0;
}